{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structures\n",
    "\n",
    "## 1 Introduction to Data Structures\n",
    "\n",
    "A data structure is a model where data is organized, managed and stored in a format that enables efficient access and modification of data. \n",
    "\n",
    "More precisely,\n",
    "\n",
    "* **a data structure is a `collection of data` values, the `relationships ` them, and the `functions or operations` that can be applied to the data**\n",
    "\n",
    "There are various types of data structures commonly available. It is up to the programmer to choose which data structure to use depending on the data.\n",
    "\n",
    "The choice of a particular one can be considered based on the following points:\n",
    "\n",
    "* It must be able to `represent` the `inherent relationship` of the data in the real world.\n",
    "\n",
    "* It must be able to `process` the data `efficiently` when necessary.\n",
    "\n",
    ">`数据结构`:相互之间存在一种或多种特定关系的数据元素的集合及其相应算法\n",
    ">\n",
    ">`结构`:指数据元素之间存在的关系，分为`逻辑结构`和`存储结构`\n",
    ">\n",
    ">`逻辑结构`:反映数据元素之间的前后间关系\n",
    ">\n",
    ">`存储结构`:数据逻辑结构在计算机存储空间的存放形式\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Why study Data Structures?\n",
    ">“Bad programmers worry about the `code`. \n",
    "> \n",
    ">  Good programmers worry about `data structures and their relationships`.”\n",
    ">\n",
    ">      Linus Torvalds\n",
    "\n",
    "Time and energy are both required to process any instruction. Every CPU cycle that is saved will have an effect on both the time and energy consumed and can be put to better use in processing other instructions.\n",
    "\n",
    "A program built using improper data structures will be therefore inefficient or unnecessarily complex. It is necessary to have a good knowledge of data structures and understand where to use the best one. \n",
    "\n",
    "The study includes the description, implementation and quantitative performance analysis of the data structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Concept of a Data Type\n",
    "\n",
    "**Primitive Data Types**\n",
    "\n",
    "A primitive data type is one that is inbuilt into the programming language for defining the most basic types of data. These may be different for the various programming languages available.\n",
    "\n",
    "For example, the C programming language has inbuilt support for characters (char), integers (int, long) and real numbers (float, double).\n",
    "\n",
    "**User-Defined Data Type**\n",
    "\n",
    "User-defined data type, as the name suggests is the one that the user defines as per the requirements of the data to be stored. Most programming languages provide support for creating user-defined data types.\n",
    "\n",
    "For example, C provides support through structures (struct), unions (union) and enumerations (enum).\n",
    "\n",
    "**Abstract Data Type (ADT)**\n",
    "\n",
    "Abstract Data Types are defined by its **behaviour** from the point of view of the user of the data.\n",
    "\n",
    "It defines it in terms of possible values, operations on data, and the behaviour of these operations.\n",
    "\n",
    "For example. The user of the stack data structure only knows about the `push` and `pop` operations in a stack.\n",
    "\n",
    "They **do not care how** the push operation interacts with the memory to store the data. They only expect it to store it in the way specified.\n",
    "\n",
    "```cpp\n",
    "The Stack ADT{\n",
    "\n",
    "Data attribute：\n",
    "    the linear list of items,top of stack,bottom of the stack\n",
    "Operation:\n",
    "  Create()：Create the empty stack\n",
    "  IsEmpty()：if the stack is empty,return true，otherwise return false\n",
    "  push(item): push(add)element to the stack. The element always gets added to the `top` of the current stack items.\n",
    "  pop(item):  pop(remove) an element from the stack. The element always gets popped off `from the top` of the stack\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Common Operations in a Data Structure\n",
    "\n",
    "A data structure is only **useful** when you can perform **operations** on it, right? \n",
    "\n",
    "These are the basic operations that should be able to be performed on every data structure.\n",
    "\n",
    "**Access（访问）**\n",
    "\n",
    "* This operation handles how the elements currently stored in the structure can be accessed.\n",
    "\n",
    "**Search（查找）**\n",
    "* This operation handles finding the location of a given element of a given structure.\n",
    "\n",
    "**Insertion（插入）**\n",
    "* This operation specifies how new elements are to be added to the structure.\n",
    "\n",
    "**Deletion（删除）**\n",
    "* This operation specifies how existing elements can be removed from the structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Classification of data structure\n",
    "\n",
    "A data structure can be broadly classified into 2 types:\n",
    "    \n",
    "* Linear Data Structures(线性）     \n",
    "* Non-Linear Data Structures（非线性）     \n",
    "\n",
    "\n",
    "#### 1.4.1 Linear Data Structures\n",
    "\n",
    "A linear data structure’s elements form a sequence. Every element in the structure has some element before and after it.\n",
    "\n",
    "> 线性：数据结构中的元素存在一对一的相互关系\n",
    "\n",
    "Examples of linear structures are:\n",
    "\n",
    "**Arrays（数组）**\n",
    "* An array holds a `fixed` number of similar elements that are stored under one name. \n",
    "\n",
    "These elements are stored in `contagious` memory locations . The elements of an array can be accessed using one `identifier`..\n",
    "\n",
    "**Linked Lists（链表）**\n",
    "* A linked list is a linear data structure where each element is a `separate` object, known as a `node` .\n",
    "\n",
    "Each node contains some `data and points` to the next node in the structure, `forming a sequence` .\n",
    "\n",
    "**Stacks（栈）**\n",
    "* Stacks are a type of linear data structures that store data in an **order** known as the **Last In First Out (LIFO)** order. \n",
    "\n",
    "This property is helpful in certain programming cases where the data needs to be ordered.\n",
    "\n",
    "**Queues（队列）**\n",
    "* Queues are a type of linear data structures that store data in an order known as the **First In First Out (FIFO)** order.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.4.2  Non-Linear Data Structures\n",
    "\n",
    "non-linear data structure’s elements do not form a sequence. Every element **may not have a unique element** before and after it.\n",
    "\n",
    ">数据结构中的元素具有多个对应关系\n",
    "\n",
    "**Trees（树）**\n",
    "\n",
    "* A tree is a data structure that simulates a `hierarchical` tree, with a `root` value and the `children` as the `subtrees`, represented by `a set of linked nodes`.\n",
    "\n",
    "**Heaps（堆）**\n",
    "\n",
    "* A heap is a complete binary tree that satisfies the  heap property. \n",
    ">The heap property says that is the value of Parent is either greater than or equal to (in a max heap ) or >less than or equal to (in a min heap) the value of the Child.\n",
    "\n",
    "**Graphs（图）**\n",
    "\n",
    "* A graph data structure is used to represent `relations` between `pairs` of objects.\n",
    "\n",
    "It consists of `nodes` (known as vertices) that are `connected` through `links` (known as edges).\n",
    "\n",
    "The relationship between the nodes can be used to model the relation between the objects in the graph.\n",
    "\n",
    "**Hash Tables（散列表/哈希表）**\n",
    "\n",
    "* A Hash Table is a data structure where data is stored in an `associative` manner.\n",
    "\n",
    "The data is `mapped` to `array positions` by a `hash function` that generates a `unique` value from each `key`.\n",
    "\n",
    "The value stored in a hash table can then be **searched in $O(1)$ time** using the same hash function which generates an address from the key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Linear Data Structures\n",
    "\n",
    "A linked structure consists of items that are linked to other items. \n",
    "\n",
    "Although many links among items are possible, the two simplest linked structures are `the singly linked structure` and `the doubly linked structure.`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Single Linked List(单向链表）\n",
    "\n",
    "The linked list consists of a series of structures, which are not necessarily adjacent in memory.\n",
    "\n",
    "Each structure contains the element and a pointer to a structure containing its successor. We call this\n",
    "the `next` pointer.\n",
    "\n",
    "The `last` cell's next pointer points to: this value is defined by C and cannot be confused with another pointer. ANSI C\n",
    "specifies that is **zero**.\n",
    "\n",
    "![](./img/ds/DS_SingleLinkedList.png)\n",
    "\n",
    "A user of a singly linked structure accesses the first item by following a single external `head` link. \n",
    "\n",
    "The user then accesses other items by chaining through `the single links` (represented by arrows in the figure) that emanate from the items. Thus, in a singly linked structure, it is easy to get to the `successor` of an item, but not so easy to get to the `predecessor` of an item.\n",
    "\n",
    "**Operations in a Linked List**\n",
    "\n",
    "The few basic operations in a linked list including adding, deleting and modifying.\n",
    "\n",
    "* Create an empty list without any node\n",
    "\n",
    "* Remove all the dynamically allocated nodes\n",
    "\n",
    "* Is list empty?\n",
    "\n",
    "* Push the data in `front` by dynamically allocate a new node\n",
    "\n",
    "* Push the data at the `end` by dynamically allocate a new node\n",
    "\n",
    "* Pop and the data at the `end` to value and remove the node\n",
    "* Pop and the data in `front` to value and remove the node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/include/node.h\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/include/node.h\n",
    "#ifndef NODE_H\n",
    "#define NODE_H\n",
    "\n",
    "template <typename T>\n",
    "class List; // Forward reference\n",
    "\n",
    "template <typename T>\n",
    "class Node\n",
    "{\n",
    "private:\n",
    "   T data;\n",
    "   Node *nextPtr;\n",
    "\n",
    "public:\n",
    "   Node(T d) : data(d), nextPtr(0){};           // Constructor\n",
    "   T getData() const { return data; };          // Public getter for data\n",
    "   Node *getNextPtr() const { return nextPtr; } // Public getter for nextPtr\n",
    "\n",
    "   friend class List<T>; // Make List class a friend to access private data\n",
    "};\n",
    "\n",
    "#endif"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/include/list.h\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/include/list.h\n",
    "#ifndef LIST_H\n",
    "#define LIST_H\n",
    "\n",
    "#include <iostream>\n",
    "#include \"Node.h\"\n",
    "\n",
    "// Forward Reference\n",
    "template <typename T>\n",
    "std::ostream &operator<<(std::ostream &os, const List<T> &lst);\n",
    "\n",
    "template <typename T>\n",
    "class List\n",
    "{\n",
    "private:\n",
    "   Node<T> *frontPtr; // First node\n",
    "   Node<T> *backPtr;  // Last node\n",
    "public:\n",
    "   List();  // Constructor\n",
    "   ~List(); // Destructor\n",
    "   void pushFront(const T &value);\n",
    "   void pushBack(const T &value);\n",
    "   bool popFront(T &value);\n",
    "   bool popBack(T &value);\n",
    "   bool isEmpty() const;\n",
    "\n",
    "   friend std::ostream &operator<<<>(std::ostream &os, const List<T> &lst);\n",
    "   // Overload the stream insertion operator to print the list\n",
    "};\n",
    "\n",
    "// Constructor - Create an empty list without any node\n",
    "template <typename T>\n",
    "List<T>::List() : frontPtr(0), backPtr(0) {}\n",
    "\n",
    "// Destructor - Remove all the dynamically allocated nodes\n",
    "template <typename T>\n",
    "List<T>::~List()\n",
    "{\n",
    "   while (frontPtr)\n",
    "   {\n",
    "      Node<T> *tempPtr = frontPtr;\n",
    "      frontPtr = frontPtr->nextPtr;\n",
    "      delete tempPtr;\n",
    "   }\n",
    "   // std::cout << \"Destructor completed...\" << std::endl;\n",
    "}\n",
    "\n",
    "// Is list empty? Check if frontPtr is null\n",
    "template <typename T>\n",
    "bool List<T>::isEmpty() const { return frontPtr == 0; }\n",
    "\n",
    "// Push the data in front by dynamically allocate a new node\n",
    "template <typename T>\n",
    "void List<T>::pushFront(const T &value)\n",
    "{\n",
    "   Node<T> *newNodePtr = new Node<T>(value);\n",
    "   if (isEmpty())\n",
    "   {\n",
    "      frontPtr = backPtr = newNodePtr;\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      newNodePtr->nextPtr = frontPtr;\n",
    "      frontPtr = newNodePtr;\n",
    "   }\n",
    "}\n",
    "\n",
    "// Push the data at the end by dynamically allocate a new node\n",
    "template <typename T>\n",
    "void List<T>::pushBack(const T &value)\n",
    "{\n",
    "   Node<T> *newNodePtr = new Node<T>(value);\n",
    "   if (isEmpty())\n",
    "   {\n",
    "      frontPtr = backPtr = newNodePtr;\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      backPtr->nextPtr = newNodePtr;\n",
    "      backPtr = newNodePtr;\n",
    "   }\n",
    "}\n",
    "\n",
    "// Pop and the data in front to value and remove the node\n",
    "template <typename T>\n",
    "bool List<T>::popFront(T &value)\n",
    "{\n",
    "   if (isEmpty())\n",
    "   {\n",
    "      return false;\n",
    "   }\n",
    "   else if (frontPtr == backPtr)\n",
    "   { // only one node\n",
    "      value = frontPtr->data;\n",
    "      delete frontPtr;        // remove node\n",
    "      frontPtr = backPtr = 0; // empty\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      value = frontPtr->data;\n",
    "      Node<T> *tempPtr = frontPtr;\n",
    "      frontPtr = frontPtr->nextPtr;\n",
    "      delete tempPtr;\n",
    "   }\n",
    "   return true;\n",
    "}\n",
    "\n",
    "// Pop and the data at the end to value and remove the node\n",
    "template <typename T>\n",
    "bool List<T>::popBack(T &value)\n",
    "{\n",
    "   if (isEmpty())\n",
    "   {\n",
    "      return false;\n",
    "   }\n",
    "   else if (frontPtr == backPtr)\n",
    "   { // only one node\n",
    "      value = backPtr->data;\n",
    "      delete backPtr;         // remove node\n",
    "      frontPtr = backPtr = 0; // empty\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      // Locate second to last node\n",
    "      Node<T> *currentPtr = frontPtr;\n",
    "      while (currentPtr->nextPtr != backPtr)\n",
    "      {\n",
    "         currentPtr = currentPtr->nextPtr;\n",
    "      }\n",
    "      value = backPtr->data;\n",
    "      delete backPtr; // remove last node\n",
    "      backPtr = currentPtr;\n",
    "      currentPtr->nextPtr = 0;\n",
    "   }\n",
    "   return true;\n",
    "}\n",
    "\n",
    "// Overload the stream insertion operator to print the list\n",
    "template <typename T>\n",
    "std::ostream &operator<<(std::ostream &os, const List<T> &lst)\n",
    "{\n",
    "   os << '{';\n",
    "   if (!lst.isEmpty())\n",
    "   {\n",
    "      Node<T> *currentPtr = lst.frontPtr;\n",
    "      while (currentPtr)\n",
    "      {\n",
    "         os << currentPtr->getData();\n",
    "         if (currentPtr != lst.backPtr)\n",
    "            os << ',';\n",
    "         currentPtr = currentPtr->getNextPtr();\n",
    "      }\n",
    "   }\n",
    "   os << '}';\n",
    "}\n",
    "\n",
    "#endif\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**TestList.cpp**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/TestList.cpp\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/TestList.cpp\n",
    "\n",
    "/*\n",
    "Test Driver for List class (TestList.cpp) \n",
    "*/\n",
    "#include <iostream>\n",
    "#include \"List.h\"\n",
    "using namespace std;\n",
    " \n",
    "int main() {\n",
    " \n",
    "   List<int> lst1;\n",
    "   cout << lst1 << endl;\n",
    "   lst1.pushFront(8);\n",
    "   lst1.pushBack(88);\n",
    "   lst1.pushFront(9);\n",
    "   lst1.pushBack(99);\n",
    "   cout << lst1 << endl;\n",
    " \n",
    "   int result;\n",
    "   lst1.popBack(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "   lst1.popBack(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "  \n",
    "   lst1.popFront(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "   lst1.popFront(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "   \n",
    "    lst1.popBack(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++  -w -o ./demo/bin/TestList ./demo/src/TestList.cpp -I./demo/include/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\TestList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2  Double Linked List(双向链表）\n",
    "\n",
    "Sometimes it is convenient to traverse lists backwards. The standard implementation does not help here, but the solution is simple.\n",
    "\n",
    "* Merely add an `extra` field to the data structure, containing `a pointer to the previous` cell.\n",
    "\n",
    "The cost of this is an extra link, which adds to the space requirement and also doubles the cost of insertions and deletions because there are more pointers to fix. \n",
    "\n",
    "On the other hand, it simplifies deletion, because you no longer have to refer to a key by using a pointer to the previous cell; this information is now at hand.\n",
    "\n",
    "![](./img/ds/DS_DoubleLinkedList.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Operations in a Double Linked List**\n",
    "\n",
    "\n",
    "* Create an empty list without any node\n",
    "\n",
    "* Remove all the dynamically allocated nodes\n",
    "\n",
    "* Is list empty?\n",
    "\n",
    "* Push the data in `front` by dynamically allocate a new node\n",
    "\n",
    "* Push the data at the `end` by dynamically allocate a new node\n",
    "\n",
    "* Pop and the data at the `end` to value and remove the node\n",
    "* Pop and the data in `front` to value and remove the node\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2.1 Double Linked List in CPP\n",
    "\n",
    "**DoubleLinkedNode.h**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/include/DoubleLinkedNode.h\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/include/DoubleLinkedNode.h\n",
    "/* \n",
    "  DoubleLinkedNode template class for double linked list (DoubleLinkedNode.h)\n",
    "*/\n",
    "#ifndef DOUBLE_LINKED_NODE_H\n",
    "#define DOUBLE_LINKED_NODE_H\n",
    "\n",
    "template <typename T>\n",
    "class DoubleLinkedList; // Forward reference\n",
    "\n",
    "template <typename T>\n",
    "class DoubleLinkedNode\n",
    "{\n",
    "private:\n",
    "   T data;\n",
    "   DoubleLinkedNode *nextPtr;\n",
    "   DoubleLinkedNode *prevPtr;\n",
    "\n",
    "public:\n",
    "   DoubleLinkedNode(T d) : data(d), nextPtr(0), prevPtr(0){};\n",
    "   T getData() const { return data; };\n",
    "   DoubleLinkedNode *getNextPtr() const { return nextPtr; }\n",
    "   DoubleLinkedNode *getPrevPtr() const { return prevPtr; }\n",
    "\n",
    "   friend class DoubleLinkedList<T>;\n",
    "   // Make DoubleLinkedList class a friend to access private data\n",
    "};\n",
    "\n",
    "#endif\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**DoubleLinkedList.h**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/include/DoubleLinkedList.h\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/include/DoubleLinkedList.h\n",
    "/* \n",
    "    DoubleLinkedList template class for double linked list\n",
    "   (DoubleLinkedList.h)\n",
    "*/\n",
    "#ifndef DOUBLE_LINKED_LIST_H\n",
    "#define DOUBLE_LINKED_LIST_H\n",
    "\n",
    "#include <iostream>\n",
    "#include \"DoubleLinkedNode.h\"\n",
    "\n",
    "// Forward Reference\n",
    "template <typename T>\n",
    "std::ostream &operator<<(std::ostream &os,\n",
    "                         const DoubleLinkedList<T> &lst);\n",
    "\n",
    "template <typename T>\n",
    "class DoubleLinkedList\n",
    "{\n",
    "private:\n",
    "   DoubleLinkedNode<T> *frontPtr;\n",
    "   DoubleLinkedNode<T> *backPtr;\n",
    "\n",
    "public:\n",
    "   DoubleLinkedList();  // Constructor\n",
    "   ~DoubleLinkedList(); // Destructor\n",
    "   void pushFront(const T &value);\n",
    "   void pushBack(const T &value);\n",
    "   bool popFront(T &value);\n",
    "   bool popBack(T &value);\n",
    "   bool isEmpty() const;\n",
    "\n",
    "   friend std::ostream &operator<<<>(std::ostream &os,\n",
    "                                     const DoubleLinkedList<T> &lst);\n",
    "   // Overload the stream insertion operator to print the list\n",
    "};\n",
    "\n",
    "// Constructor - Create an empty list with no node\n",
    "template <typename T>\n",
    "DoubleLinkedList<T>::DoubleLinkedList() : frontPtr(0), backPtr(0) {}\n",
    "\n",
    "// Destructor - Remove all the dynamically allocated nodes\n",
    "template <typename T>\n",
    "DoubleLinkedList<T>::~DoubleLinkedList()\n",
    "{\n",
    "   while (frontPtr)\n",
    "   {\n",
    "      DoubleLinkedNode<T> *tempPtr = frontPtr;\n",
    "      frontPtr = frontPtr->nextPtr;\n",
    "      delete tempPtr;\n",
    "   }\n",
    "   // std::cout << \"Destructor completed...\" << std::endl;\n",
    "}\n",
    "\n",
    "// Is list empty? Check if frontPtr is null\n",
    "template <typename T>\n",
    "bool DoubleLinkedList<T>::isEmpty() const { return frontPtr == 0; }\n",
    "\n",
    "// Push the data in front by dynamically allocate a new node\n",
    "template <typename T>\n",
    "void DoubleLinkedList<T>::pushFront(const T &value)\n",
    "{\n",
    "   DoubleLinkedNode<T> *newPtr = new DoubleLinkedNode<T>(value);\n",
    "   if (isEmpty())\n",
    "   {\n",
    "      frontPtr = backPtr = newPtr;\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      frontPtr->prevPtr = newPtr;\n",
    "      newPtr->nextPtr = frontPtr;\n",
    "      frontPtr = newPtr;\n",
    "   }\n",
    "}\n",
    "\n",
    "// Push the data at the end by dynamically allocate a new node\n",
    "template <typename T>\n",
    "void DoubleLinkedList<T>::pushBack(const T &value)\n",
    "{\n",
    "   DoubleLinkedNode<T> *newPtr = new DoubleLinkedNode<T>(value);\n",
    "   if (isEmpty())\n",
    "   {\n",
    "      frontPtr = backPtr = newPtr;\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      backPtr->nextPtr = newPtr;\n",
    "      newPtr->prevPtr = backPtr;\n",
    "      backPtr = newPtr;\n",
    "   }\n",
    "}\n",
    "\n",
    "// Pop and the data in front to value and remove the node\n",
    "template <typename T>\n",
    "bool DoubleLinkedList<T>::popFront(T &value)\n",
    "{\n",
    "   if (isEmpty())\n",
    "   {\n",
    "      return false;\n",
    "   }\n",
    "   else if (frontPtr == backPtr)\n",
    "   { // only one node\n",
    "      value = frontPtr->data;\n",
    "      delete frontPtr;        // remove node\n",
    "      frontPtr = backPtr = 0; // empty\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      value = frontPtr->data;\n",
    "      DoubleLinkedNode<T> *tempPtr = frontPtr;\n",
    "      frontPtr = frontPtr->nextPtr;\n",
    "      frontPtr->prevPtr = 0;\n",
    "      delete tempPtr;\n",
    "   }\n",
    "   return true;\n",
    "}\n",
    "\n",
    "// Pop and the data at the end to value and remove the node\n",
    "template <typename T>\n",
    "bool DoubleLinkedList<T>::popBack(T &value)\n",
    "{\n",
    "   if (isEmpty())\n",
    "   {\n",
    "      return false;\n",
    "   }\n",
    "   else if (frontPtr == backPtr)\n",
    "   { // only one node\n",
    "      value = backPtr->data;\n",
    "      delete backPtr;         // remove node\n",
    "      frontPtr = backPtr = 0; // empty\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      value = backPtr->data;\n",
    "      DoubleLinkedNode<T> *tempPtr = backPtr;\n",
    "      backPtr = backPtr->prevPtr; // 2nd last node\n",
    "      backPtr->nextPtr = 0;\n",
    "      delete tempPtr;\n",
    "   }\n",
    "   return true;\n",
    "}\n",
    "\n",
    "// Overload the stream insertion operator to print the list\n",
    "template <typename T>\n",
    "std::ostream &operator<<(std::ostream &os, const DoubleLinkedList<T> &lst)\n",
    "{\n",
    "   os << '{';\n",
    "   if (!lst.isEmpty())\n",
    "   {\n",
    "      DoubleLinkedNode<T> *currentPtr = lst.frontPtr;\n",
    "      while (currentPtr)\n",
    "      {\n",
    "         os << currentPtr->getData();\n",
    "         if (currentPtr != lst.backPtr)\n",
    "            os << ',';\n",
    "         currentPtr = currentPtr->getNextPtr();\n",
    "      }\n",
    "   }\n",
    "   os << '}';\n",
    "}\n",
    "\n",
    "#endif\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**TestDoubleLinkedList.cpp**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/TestDoubleLinkedList.cpp\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/TestDoubleLinkedList.cpp\n",
    "\n",
    "/* \n",
    " Test Driver for List class (TestDoubleLinkedList.cpp) \n",
    "*/\n",
    "#include <iostream>\n",
    "#include \"DoubleLinkedList.h\"\n",
    "using namespace std;\n",
    " \n",
    "int main() {\n",
    " \n",
    "   DoubleLinkedList<int> lst1;\n",
    "   cout << lst1 << endl;\n",
    "   lst1.pushFront(8);\n",
    "   lst1.pushBack(88);\n",
    "    \n",
    "   lst1.pushFront(9);\n",
    "   lst1.pushBack(99);\n",
    "   \n",
    "    cout << lst1 << endl;\n",
    " \n",
    "   int result;\n",
    "   lst1.popBack(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "   lst1.popBack(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "  \n",
    "   lst1.popFront(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "   lst1.popFront(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "   \n",
    "   lst1.popBack(result)\n",
    "      ? cout << \"value is \" << result << \", list is \" << lst1 << endl\n",
    "      : cout << \"empty list\" << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -w -o ./demo/bin/TestDoubleLinkedList ./demo/src/TestDoubleLinkedList.cpp -I./demo/include/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{9,8,88,99}\n",
      "value is 99, list is {9,8,88}\n",
      "value is 88, list is {9,8}\n",
      "value is 9, list is {8}\n",
      "value is 8, list is {}\n",
      "empty list\n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\TestDoubleLinkedList "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2.2 std:list\n",
    "\n",
    "The `std::list` is implemented as a `doubly-linked` list. This means list data can be accessed bi-directionally and sequentially."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/demo_std_list.cpp\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/demo_std_list.cpp\n",
    "#include <algorithm>\n",
    "#include <iostream>\n",
    "#include <list>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "int main() {\n",
    "\tlist<int> my_list = { };\n",
    "\tmy_list.push_front(8);\n",
    "\tmy_list.push_back(88);\n",
    "    my_list.push_front(9);\n",
    "    my_list.push_back(99);\n",
    "    \n",
    "    for (int x : my_list) {\n",
    "\t\tcout << x << ' ';\n",
    "\t}\n",
    "   cout <<endl;\n",
    "    \n",
    "\tauto it =find(my_list.begin(), my_list.end(), 88);\n",
    "\tif (it != my_list.end()) {\n",
    "\t\tmy_list.insert(it, 21);\n",
    "\t}\n",
    "    \n",
    "\tfor (int x : my_list) {\n",
    "\t\tcout << x << ' ';\n",
    "\t}\n",
    "    cout <<endl;\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -o ./demo/bin/demo_std_list ./demo/src/demo_std_list.cpp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 8 88 99 \n",
      "9 8 21 88 99 \n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\demo_std_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Stack(栈LIFO)\n",
    "\n",
    "#### 2.3.1 Overview of Stacks\n",
    "\n",
    "Stacks are linear collections in which **access** is completely restricted to just **one end**, called the **top**. \n",
    "\n",
    "The classic analogous example is the stack of clean trays found in every cafeteria. Whenever a tray is needed, it is removed from the top of the stack, and whenever clean ones come back from the kitchen, they are again placed on the top. No one ever takes some particularly fine tray from the middle of the stack, and trays near the bottom might never be used.\n",
    "\n",
    "Stacks are said to adhere to a last-in first-out (LIFO) protocol. The last tray brought back from the dishwasher is the first one a customer takes.\n",
    "\n",
    "The two primary operations for putting items on and removing items from a stack are called **push** and **pop**, respectively. \n",
    "\n",
    "1. **Push（入栈）** Operation\n",
    "\n",
    "  * This is used to add (or `push`) an element to the stack. The element always gets added to the `top` of the current stack items.\n",
    "\n",
    "2. **Pop（出栈）** Operation\n",
    "  * This is used to remove (or `pop`) an element from the stack. The element always gets popped off `from the top` of the stack\n",
    "\n",
    "\n",
    "The Figure shows a stack as it might appear at various stages. The item at the top of the stack is shaded.\n",
    "\n",
    "![](./img/ds/stacklife.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.3.2 Implementations of Stacks\n",
    "\n",
    "Because of their simple behavior and linear structure, stacks are implemented easily using arrays or linked structures.\n",
    "\n",
    "##### 2.3.2.1 List Implementation of Stacks in Python\n",
    "\n",
    "We implement the stack using a list where the top is at the beginning\n",
    "\n",
    "so,we  have to index position 0 (the first item in the list) explicitly using pop and insert. \n",
    "\n",
    "The implementation is shown below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    def is_empty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def push(self, item):\n",
    "        self.items.insert(0, item)\n",
    "\n",
    "    def pop(self):\n",
    "        return self.items.pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "s = Stack()\n",
    "s.push(88)\n",
    "s.push(8)\n",
    "print(s.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2.3.2.2 from queue import LifoQueue\n",
    "\n",
    ">queue — A synchronized queue class\n",
    ">\n",
    ">* https://docs.python.org/3/library/queue.html\n",
    ">\n",
    ">The queue module defines the following classes and exceptions:\n",
    ">\n",
    ">**class queue.Queue(maxsize=0)-队列**\n",
    ">\n",
    ">Constructor for a FIFO queue. maxsize is an integer that sets the upperbound limit on the number of items that can be placed in the queue. Insertion will block once this size has been reached, until queue items are consumed. If maxsize is less than or equal to zero, the queue size is infinite.\n",
    ">\n",
    ">**class queue.LifoQueue(maxsize=0)-栈**\n",
    ">\n",
    ">Constructor for a LIFO queue. maxsize is an integer that sets the upperbound limit on the number of items that can be placed in the queue. Insertion will block once this size has been reached, until queue items are consumed. If maxsize is less than or equal to zero, the queue size is infinite.\n",
    ">\n",
    ">**class queue.PriorityQueue(maxsize=0)-最小堆**\n",
    ">\n",
    ">Constructor for a priority queue. maxsize i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "LIFO [88, 8]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from queue import LifoQueue\n",
    "lifoQueue = LifoQueue()\n",
    "lifoQueue.put(88)\n",
    "lifoQueue.put(8)\n",
    "print('LIFO', lifoQueue.queue)\n",
    "lifoQueue.get()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Simple Balance Parentheses**\n",
    "\n",
    "We now turn our attention to using stacks to solve real computer science problems. You have\n",
    "no doubt written arithmetic expressions such as\n",
    "\n",
    "$(5 + 6) * (7 + 8)/(4 + 3)$\n",
    "\n",
    "where parentheses are used to order the performance of operation\n",
    "\n",
    "The stack is the appropriate data structure for keeping the parentheses,\n",
    "\n",
    "Starting with an `empty` stack, process the parenthesis strings from left to right. \n",
    "\n",
    "If a symbol is an `opening` parenthesis, it on the `stack` as a signal that a corresponding closing symbol needs to appear later.\n",
    "\n",
    "If, on the other hand, a symbol is a `closing` parenthesis, `pop` the stack.\n",
    "\n",
    "As long as it is possible to pop the stack to match every closing symbol, the parentheses remain balanced.\n",
    "\n",
    "If at any time there is no opening symbol on the stack to match a closing symbol, the string is not balanced prop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def par_checker(symbol_string):\n",
    "    s = Stack()\n",
    "    balanced = True\n",
    "    index = 0\n",
    "    while index < len(symbol_string) and balanced:\n",
    "        symbol = symbol_string[index]\n",
    "        if symbol == \"(\":\n",
    "            s.push(symbol)\n",
    "        elif symbol == \")\" and (not s.is_empty()):\n",
    "             s.pop()\n",
    "        index = index + 1\n",
    "\n",
    "    if balanced and s.is_empty():\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(par_checker('((()))'))\n",
    "print(par_checker('((())'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(par_checker('(5 + 6) * (7 + 8)/(4 + 3)'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2.3.2.3 Array Implementation of Stacks in CPP\n",
    "\n",
    "we need to declare:\n",
    "*  an array:`T *data`\n",
    "*  an array size ahead of time: `int capacity`\n",
    "*  Top of stack, start at index -1: `int tos`\n",
    "\n",
    "The two primary operations:  push and pop, .\n",
    "\n",
    "*  push(const T & value)\n",
    "* pop(T & value)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Stack.h**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/include/Stack.h\n",
    "\n",
    "#ifndef STACK_H\n",
    "#define STACK_H\n",
    "\n",
    "#include <iostream>\n",
    "\n",
    "// Forward Reference\n",
    "template <typename T>\n",
    "class Stack;\n",
    "template <typename T>\n",
    "std::ostream &operator<<(std::ostream &os, const Stack<T> &s);\n",
    "\n",
    "template <typename T>\n",
    "class Stack\n",
    "{\n",
    "private:\n",
    "   T *data;       // Array\n",
    "   int tos;       // Top of stack, start at index -1\n",
    "   int capacity;  // capacity of the array\n",
    "   int increment; // each subsequent increment size\n",
    "public:\n",
    "   explicit Stack(int capacity = 10, int increment = 10);\n",
    "   ~Stack(); // Destructor\n",
    "   void push(const T &value);\n",
    "   bool pop(T &value);\n",
    "   bool isEmpty() const;\n",
    "\n",
    "   friend std::ostream &operator<<<>(std::ostream &os, const Stack<T> &s);\n",
    "   // Overload the stream insertion operator to print the list\n",
    "};\n",
    "\n",
    "// Constructor - Create an empty list without any node\n",
    "template <typename T>\n",
    "Stack<T>::Stack(int cap, int inc) : capacity(cap), increment(inc)\n",
    "{\n",
    "   data = new T[capacity];\n",
    "   tos = -1;\n",
    "}\n",
    "\n",
    "// Destructor - Remove all the dynamically allocated nodes\n",
    "template <typename T>\n",
    "Stack<T>::~Stack()\n",
    "{\n",
    "   delete[] data; // remove the dynamically allocate storage\n",
    "   // std::cout << \"Destructor completed...\" << std::endl;\n",
    "}\n",
    "\n",
    "// Is list empty? Check if frontPtr is null\n",
    "template <typename T>\n",
    "bool Stack<T>::isEmpty() const { return tos < 0; }\n",
    "\n",
    "// Push the data on top of the stack\n",
    "template <typename T>\n",
    "void Stack<T>::push(const T &value)\n",
    "{\n",
    "   if (tos < capacity - 1)\n",
    "   {\n",
    "      // Have space, simply add in the value\n",
    "      data[++tos] = value;\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      // No more space. Allocate a bigger array\n",
    "      T *newDataPtr = new T[capacity + increment];\n",
    "      for (int i = 0; i <= tos; ++i)\n",
    "      {\n",
    "         newDataPtr[i] = data[i]; // copy over\n",
    "      }\n",
    "      delete[] data;\n",
    "      data = newDataPtr;\n",
    "   }\n",
    "}\n",
    "\n",
    "// Pop the data from the TOS\n",
    "template <typename T>\n",
    "bool Stack<T>::pop(T &value)\n",
    "{\n",
    "   if (isEmpty())\n",
    "   {\n",
    "      return false;\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      value = data[tos--];\n",
    "   }\n",
    "   return true;\n",
    "}\n",
    "\n",
    "// Overload the stream insertion operator to print the list\n",
    "template <typename T>\n",
    "std::ostream &operator<<(std::ostream &os, const Stack<T> &stack)\n",
    "{\n",
    "   os << '{';\n",
    "   for (int i = stack.tos; i >= 0; --i)\n",
    "   {\n",
    "      os << stack.data[i];\n",
    "      if (i > 0)\n",
    "         os << ',';\n",
    "   }\n",
    "   os << '}';\n",
    "}\n",
    "\n",
    "#endif\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/TestStack.cpp\n",
    "/* \n",
    "  Test Driver for Stack class (TestStack.cpp)\n",
    "    \n",
    "*/\n",
    "#include <iostream>\n",
    "#include \"Stack.h\"\n",
    "using namespace std;\n",
    " \n",
    "int main() {\n",
    " \n",
    "   Stack<int> s1;\n",
    "   cout << s1 << endl;\n",
    "   s1.push(8);\n",
    "   s1.push(88);\n",
    "   cout << s1 << endl;\n",
    " \n",
    "   int result;\n",
    "   s1.pop(result)\n",
    "      ? cout << \"value is \" << result << \", stack is \" << s1 << endl\n",
    "      : cout << \"empty stack\" << endl;\n",
    " \n",
    "   s1.push(9);\n",
    "   s1.push(99);\n",
    "   cout << s1 << endl;\n",
    " \n",
    "   s1.pop(result)\n",
    "      ? cout << \"value is \" << result << \", stack is \" << s1 << endl\n",
    "      : cout << \"empty stack\" << endl;\n",
    " \n",
    "   s1.pop(result)\n",
    "      ? cout << \"value is \" << result << \", stack is \" << s1 << endl\n",
    "      : cout << \"empty stack\" << endl;\n",
    "   s1.pop(result)\n",
    "      ? cout << \"value is \" << result << \", stack is \" << s1 << endl\n",
    "      : cout << \"empty stack\" << endl;\n",
    "   s1.pop(result)\n",
    "      ? cout << \"value is \" << result << \", stack is \" << s1 << endl\n",
    "      : cout << \"empty stack\" << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -w -o ./demo/bin/TestStack ./demo/src/TestStack.cpp -I./demo/include/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\TestStack "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2.3.2.4 std::stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Writing ./demo/src/demo_std_stack.cpp\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/demo_std_stack.cpp\n",
    "#include <iostream> \n",
    "#include <stack> \n",
    "using namespace std;\n",
    "\n",
    "int main() {\n",
    "\tstack<int> st;\n",
    "\tst.push(8);\n",
    "\tst.push(88);\n",
    "\n",
    "    while (!st.empty()) {\n",
    "\t\tcout << ' ' << st.top();\n",
    "\t\tst.pop();\n",
    "\t}\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -o ./demo/bin/demo_std_stack ./demo/src/demo_std_stack.cpp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 88 8\n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\demo_std_stack "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 Queue(队列 FIFO)\n",
    "\n",
    "#### 2.4.1 Overview Of Queue\n",
    "\n",
    "Like stacks, queues are linear collections. However, with queues, **insertions** are restricted to **one end**, called the **rear**, and removals to the other end, called the **front**.\n",
    "\n",
    "A queue thus supports **a first-in first-out (FIFO)** protocol. \n",
    "\n",
    "Queues are omnipresent in everyday life and occur in any situation where people or things are lined up for service or processing on a\n",
    "first-come, first-served basis. Checkout lines in stores, highway tollbooth lines, and airport baggage check-in lines are familiar examples of queues.\n",
    "\n",
    "\n",
    "![Queue](./img/ds/queue.png)\n",
    "\n",
    "\n",
    "**Basic Operation**\n",
    "\n",
    "Queues have two fundamental operations: \n",
    "\n",
    "* add(Enqueue-入队）, which adds an item to the `rear` of a queue, and\n",
    "\n",
    "* pop(Dequeue-出队）, which removes an item from the `front`. \n",
    "\n",
    "\n",
    "![Enqueue](./img/ds/enqueue.png)\n",
    "\n",
    "\n",
    "![dequeue](./img/ds/dequeue.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.4.2 Implementation of Queue \n",
    "\n",
    "##### 2.4.2.1 List Implementation of Queue in Python\n",
    "\n",
    "We use the append function on lists to add new elements to the end of the queue\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    def is_empty(self):\n",
    "        return self.items == []\n",
    "    def enqueue(self, item):\n",
    "        self.items.append(item)\n",
    "    def dequeue(self):\n",
    "        return self.items.pop(0)   \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = Queue()\n",
    "q.enqueue('88')\n",
    "q.enqueue('8')\n",
    "q.dequeue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**from queue import Queue**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from queue import Queue\n",
    " \n",
    "q = Queue()\n",
    "q.put(88)\n",
    "q.put(8)\n",
    "print('FIFO', q.queue)    # [0, 5, 3]\n",
    " \n",
    "head = q.get()\n",
    "print(head)\n",
    "print(q.queue)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " **Plotting Live data with deque in Jupyter notebook**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "psutil: Cross-platform lib for process and system monitoring in Python\n",
    "\n",
    "https://github.com/giampaolo/psutil\n",
    "```\n",
    "python -m pip install psutil\n",
    "```\n",
    "\n",
    "IPython.display\n",
    "\n",
    "```python\n",
    "from IPython.display import clear_output\n",
    "\n",
    "clear_output(wait=True)\n",
    "```\n",
    "to avoid the problem： screen **flicker** in figure dynamic display"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Il7ecAAAACXBIWXMAAAsTAAALEwEAmpwYAAAXeklEQVR4nO3df5BV9X3/8edLFkQQi+gG+YL8+FaEWmciuGNNrJkE1NHYKrXWmKGRdGjotNrGmjaS2NbWxhkZbZN0JukM448vHdEGFYOlbQKhmk6mU5pFMSKoIIKB8GNrJKKogLy/f3zOustyl3t2996914+vx8yZ8+Oes/e9h8vrnv2ccz5HEYGZmX3wndDoAszMrDYc6GZmmXCgm5llwoFuZpYJB7qZWSYc6GZmmSgV6JL+VNLzkjZIeljScElTJK2VtEXSdyQNq3exZmbWu6qBLmk88CdAW0ScCwwBrgcWAV+PiLOA14H59SzUzMyOr2yTSwtwkqQWYASwC5gFPFq8vgSYU/PqzMystJZqK0TETkn3AK8CbwOrgHXAvog4XKy2AxhfaXtJC4AFACNHjjx/+vTptajbzOxDY926df8bEa3V1qsa6JJOBa4GpgD7gEeAy8sWEhGLgcUAbW1t0d7eXnZTMzMDJG0vs16ZJpdLgFcioiMiDgHLgYuA0UUTDMAEYGe/KjUzs5ooE+ivAhdKGiFJwGxgI/AkcG2xzjxgRX1KNDOzMqoGekSsJZ38fBp4rthmMXArcIukLcBpwH11rNPMzKqo2oYOEBG3A7f3WLwVuKDmFZmZWb/4TlEzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMlE10CVNk7S+2/CGpJsljZG0WtLmYnzqYBRsZmaVlXlI9IsRcV5EnAecDxwAHgcWAmsiYiqwppg3M7MG6WuTy2zg5YjYDlwNLCmWLwHm1LAuMzPro74G+vXAw8X02IjYVUzvBsbWrCozM+uz0oEuaRhwFfBIz9ciIoDoZbsFktoltXd0dPS7UDMzO76+HKFfATwdEXuK+T2SxgEU472VNoqIxRHRFhFtra2tA6vWzMx61ZdA/yxdzS0ATwDziul5wIpaFWVmZn1XKtAljQQuBZZ3W3wXcKmkzcAlxbyZmTVIS5mVIuIt4LQey14jXfViZmZNwHeKmpllwoFuZpYJB7qZWSYc6GZmmXCgm5llwoFuZpYJB7qZWSYc6GZmmXCgm5llwoFuZpYJB7qZWSYc6GZmmXCgm5llwoFuZpYJB7qZWSYc6GZmmXCgm5llwoFuZpYJB7qZWSbKPiR6tKRHJb0gaZOkj0kaI2m1pM3F+NR6F2tmZr0re4T+TeB7ETEd+CiwCVgIrImIqcCaYt7MzBqkaqBL+iXgE8B9ABFxMCL2AVcDS4rVlgBz6lOimZmVUeYIfQrQATwg6RlJ90oaCYyNiF3FOruBsZU2lrRAUruk9o6OjtpUbWZmxygT6C3ATOAfI2IG8BY9mlciIoCotHFELI6Itohoa21tHWi9ZmbWizKBvgPYERFri/lHSQG/R9I4gGK8tz4lmplZGVUDPSJ2Az+VNK1YNBvYCDwBzCuWzQNW1KVCMzMrpaXken8MLJU0DNgK/B7py2CZpPnAduC6+pRoZmZllAr0iFgPtFV4aXZNqzEzs37znaJmZplwoJuZZcKBbmaWCQe6mVkmHOhmZplwoJuZZcKBbmaWCQe6mVkmHOhmZplwoJuZZcKBbmaWCQe6mVkmHOhmZplwoJuZZcKBbmaWCQe6mVkmHOhmZplwoJuZZaLUI+gkbQP2A+8BhyOiTdIY4DvAZGAbcF1EvF6fMs3MrJq+HKF/KiLOi4jOZ4suBNZExFRgTTFvZmYNMpAml6uBJcX0EmDOgKsxM7N+KxvoAayStE7SgmLZ2IjYVUzvBsZW2lDSAkntkto7OjoGWK6ZmfWmVBs68OsRsVPSR4DVkl7o/mJEhKSotGFELAYWA7S1tVVcx8zMBq7UEXpE7CzGe4HHgQuAPZLGARTjvfUq0szMqqsa6JJGShrVOQ1cBmwAngDmFavNA1bUq0gzM6uuTJPLWOBxSZ3rPxQR35P0Y2CZpPnAduC6+pVpZmbVVA30iNgKfLTC8teA2fUoyszM+s53ipqZZcKBbmaWCQe6mVkmHOhmZplwoJuZZcKBbmaWCQe6mVkmHOhmZplwoJuZZcKBbmaWCQe6mVkmHOhmZplwoJuZZcKBbmaWCQe6mVkmHOhmZplwoJuZZcKBbmaWidKBLmmIpGckrSzmp0haK2mLpO9IGla/Ms3MrJq+HKF/EdjUbX4R8PWIOAt4HZhfy8LMzKxvSgW6pAnAlcC9xbyAWcCjxSpLgDl1qM/MzEoqe4T+DeDLwJFi/jRgX0QcLuZ3AOMrbShpgaR2Se0dHR0DqdXMzI6jaqBL+g1gb0Ss688bRMTiiGiLiLbW1tb+/AgzMyuhpcQ6FwFXSfo0MBw4BfgmMFpSS3GUPgHYWb8yzcysmqpH6BHxlYiYEBGTgeuB/4iIucCTwLXFavOAFXWr0szMqhrIdei3ArdI2kJqU7+vNiWZmVl/lGlyeV9EPAU8VUxvBS6ofUlmZtYfvlPUzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0xUDXRJwyX9j6RnJT0v6W+K5VMkrZW0RdJ3JA2rf7lmZtabMkfo7wKzIuKjwHnA5ZIuBBYBX4+Is4DXgfl1q9LMzKqqGuiRvFnMDi2GAGYBjxbLlwBz6lGgmZmVU6oNXdIQSeuBvcBq4GVgX0QcLlbZAYzvZdsFktoltXd0dNSgZDMzq6RUoEfEexFxHjABuACYXvYNImJxRLRFRFtra2v/qjQzs6r6dJVLROwDngQ+BoyW1FK8NAHYWdvSzMysL8pc5dIqaXQxfRJwKbCJFOzXFqvNA1bUqUYzMyuhpfoqjAOWSBpC+gJYFhErJW0E/lnS14BngPvqWKeZmVVRNdAj4ifAjArLt5La083MrAn4TlEzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMuFANzPLhAPdzCwTDnQzs0w40M3MMlHmIdFnSnpS0kZJz0v6YrF8jKTVkjYX41PrX66ZmfWmzBH6YeBLEXEOcCFwo6RzgIXAmoiYCqwp5s3MrEGqBnpE7IqIp4vp/cAmYDxwNbCkWG0JMKdONZqZWQl9akOXNBmYAawFxkbEruKl3cDYXrZZIKldUntHR8dAajUzs+MoHeiSTgYeA26OiDe6vxYRAUSl7SJicUS0RURba2vrgIo1M7PelQp0SUNJYb40IpYXi/dIGle8Pg7YW58SzcysjDJXuQi4D9gUEX/f7aUngHnF9DxgRe3LMzOzslpKrHMR8DngOUnri2VfBe4ClkmaD2wHrqtLhWZmVkrVQI+IHwHq5eXZtS3HzMz6y3eKmpllwoFuZpYJB7qZWSYc6GZmmXCgm5llwoFuZpYJB7qZWSYc6GZmmXCgm5llwoFuZpYJB7qZWSYc6GZmmXCgm5llwoFuZpYJB7qZWSYc6GZmmXCgm5llwoFulrGlS2HyZDjhhDReurTRFTWnXPZTmYdE3y9pr6QN3ZaNkbRa0uZifGp9yzSzvlq6FBYsgO3bISKNFyz44IZVveS0n8ocof8/4PIeyxYCayJiKrCmmDezJnLbbXDgwNHLDhyAr361MfU0m3fegQ0b4OabK++n225rSFkDUuYh0f8paXKPxVcDnyymlwBPAbfWsjAzG5hXX+19+fTpMHVqGs4+u2s8fnxqdshFBOzeDS+8AC++2DW88AJs25Ze78327XDHHXDNNfCrvwrSoJXdb1UDvRdjI2JXMb0bGFujesxsgDZuhK98pfewOuUUOPdc2LwZ1qyBt9/uem34cDjrrK6Q7x74Y8c2b6i9/Xb6fXqG9osvwv79XeuddBJMmwYXXACf+1z6YrvllhT6PZ14Ivz1X8Ptt6d9cM01aWhra9790N9Af19EhKRev+ckLQAWAEycOHGgb2dmvdi5M4XPAw/AySfD7/wOrFx5dGCPGAHf/jbMnZvmjxyBn/0MXnopBeLmzWl640b4l3+BQ4e6th01qvJR/dSpMGZM/X+/CNi16+ij7c7pzvbvTmeemYL7hhtSaE+bloYJE479C+TIkdRm3r3ZZcQIWLwYZs2C734Xli+Hu++Gu+5KP7sz3C+6CIYMqf/vXpbieH9zdK6UmlxWRsS5xfyLwCcjYpekccBTETGt2s9pa2uL9vb2AZZsZt3t2weLFsE3vgHvvQc33pjaf08/PZ3Yu+221MwycSLceWdXmFdz+HDarjPku4+3bUtB2GnMmGNDvnMYNeron1utpgMHjj7a7h7gb77Ztd6IEV1B3T20zz4bRo7s2z4ss59+/vP0JffYY7BqFbz7LnzkIzBnTgr3T30Khg3r2/uWJWldRLRVXa+fgX438FpE3CVpITAmIr5c7ec40M1q55130tH2nXemsJk7F/72b2HKlPq/98GDsHXr0SHfOb1jx9HrnnFGV8i/+WY64n333a7Xhw5NYQgptF999eij7YkTjw7szgAfP75xTR/798O//3sK93/9V3jrLRg9Gn7zN1O4X3ZZ+sKplZoFuqSHSSdATwf2ALcD3wWWAROB7cB1EfHzam/mQDcbuPfeg4cegr/4ixR+l12WmgJmzGh0ZcmBA7Bly9Eh3zneu7fyNhLMnHlsaE+dWttgrId33oHVq1OzzIoV8PrrqeZPfzqF+5VXpvMWA1HTI/RacaCb9V8EfP/7cOut8JOfpABctAguuaTRlZV3wgmVT9ZKRzfhfFAdOgQ//GEK98cfTydbhw2DSy9N4X7VVakprK/KBnpGFyiZ5evHP4bZs+GKK1KzxcMPp2UfpDCH1HzSl+UfNEOHpn+Tb387naT+0Y/gppvS9e7z56fmp9mz4VvfSq/XmgPdrIlt2QKf+Uy6zO655+Af/gE2bYLrr/9gXi9+553HNqGMGJGW5+aEE9JVMH/3d/DKK7BuHSxcmK7UuemmdMXNxz8O99yTzkfUREQM2nD++eeHmVW3e3fEH/1RREtLxIgREX/5lxG/+EWjq6qNBx+MmDQpQkrjBx9sdEWDb+PGiK99LWLmzIjUCBVx3nkRd9wRsWFDxJEjab3OfQXnR5TIWLehmzWR/fvTEd0996STbV/4Qrq2/IwzGl2Z1cu2banNffly+K//SvHeeWJ41ar0OYA2ItqrXtPjQDdrAocOpRtZ7rgjXQly7bWpGeLssxtdmQ2mXbu6bmT6wQ+6v1Iu0D+ArXBm+YiAZcvgnHNSu+r06fDf/w2PPOIw/zAaNw7+8A/TZZD9ucbegW7WIE8+mU52fuYzqQ+VlSvhqafg136t0ZVZM+jPlT8OdLNB9uyz6fLDWbPSdcoPPADr16cbUJq10ycbfJWuCKrGgW42SLZvT51FzZgBa9emzp5eegk+//nm6uDJmsPcuem8yqRJ5bdxoJvV2WuvwZe+lNrEly2DP/9zePll+LM/S925mvVm7tx0FUy6ir26D22g5/IMQWsePT9TDzyQ+lj55V9OPSHOnZv6NFm0CE71QxutDj6Ugd6szxD0l0x5zbavKn2m5s9PD5q4+OLUbn7//akvbbN6GdTr0KW2mDSpvU99Mg9UROracv/+ruHKK2HPnmPXbW2Ff/qn1JnOsGGpX4ae05WWDRky8JNZnYFQqZP9wdpXvdXV3/6061nTYOyriNQn+DvvpO5e3323a7rn+IYboKPj2J8xdmzlp+GY9UVT9rYotQW0V/3Pd/BgV/i+8cbRYVx26NzuzTeP/9zAWunrl0DPZStWpC+enkaPTncKDh+eHol14old02XGw4b1/8tmML9kjhxJN9ccOpT+/Q8e7Jruuey3fqvyF/KYMfBXf9V76PZnPNDPTi69CFpjNXWgQwqGiy+uHMYHD5b7eSeemJ6GUmY45ZSu6S98oXK/zGecke7Q6i1I6rlsy5Ya7ugK++l4wd/ba0uXHv08xk6nnJKuzDje71Xt9+75+uHDtf+9W1r6/gXYl/3Tffzbv53u8utp0qTOk1pm/Vc20Af8TNH+OnAgPWVl1KjU1NFb+B5v6O/jnvbvr3zkec898LGP1eb366vJk1O7a09nnpn6vq7VEWdv4zfeOHZ5pTCHtO6SJb3/9dF9euTIcn+x9OUvmhtuqPyFPH586pGwM4QH81LAu++u/JnKsRdBa2JlevCq1QDnv9+z2KRJNe6+rI+arce3Bx9Mvep17h9I842sK/XyduzQDP92zbavOutqps+U5QNojzIZW2alWg2dgd4M//maUbMFQrMGZ2dtzbSvzOqpbKBnf5WLDUwzXuVi9mEzKCdFJV0OfBMYAtwbEXcdb313n2tm1nd1f6aopCHAt4ArgHOAz0o6p78/z8zMBmYgd4peAGyJiK0RcRD4Z+Dq2pRlZmZ9NZDLFscDP+02vwM4pidnSQuABcXsu5I2DOA96+F04H8bXUQPrqm8ZqzLNZXjmsqbVmalul+HHhGLgcUAktrLtAMNJtdUTjPWBM1Zl2sqxzWVJ6nUyceBNLnsBLp3NTShWGZmZg0wkED/MTBV0hRJw4DrgSdqU5aZmfVVv5tcIuKwpJuA75MuW7w/Ip6vstni/r5fHbmmcpqxJmjOulxTOa6pvFJ1DeqNRWZmVj8fygdcmJnlyIFuZpaJQQl0SZdLelHSFkkLB+M9q5F0v6S9zXRdvKQzJT0paaOk5yV9sQlqGi7pfyQ9W9T0N42uqZOkIZKekbSy0bUASNom6TlJ68teZjYYJI2W9KikFyRtktSgTqLfr2dasY86hzck3dzImoq6/rT4jG+Q9LCk4U1Q0xeLep4vtY/K9OA1kIF0wvRl4P8Cw4BngXPq/b4l6voEMBPY0OhautU0DphZTI8CXmr0vgIEnFxMDwXWAhc2el8V9dwCPASsbHQtRT3bgNMbXUeFupYAv19MDwNGN7qmbrUNAXYDkxpcx3jgFeCkYn4Z8PkG13QusAEYQbqA5QfAWcfbZjCO0Juyi4CI+E/g542uo7uI2BURTxfT+4FNpA9aI2uKiHizmB1aDA0/ky5pAnAlcG+ja2lmkn6JdPByH0BEHIyIfQ0t6mizgZcjosLjXQZdC3CSpBZSiP6swfX8CrA2Ig5ExGHgh8A1x9tgMAK9UhcBDQ2pDwJJk4EZpCPihiqaNtYDe4HVEdHwmoBvAF8GmumJnQGskrSu6PKiGUwBOoAHiuapeyWNbHRR3VwPPNzoIiJiJ3AP8CqwC/hFRKxqbFVsAC6WdJqkEcCnOfpmzmP4pGgTknQy8Bhwc0S80eh6IuK9iDiPdDfwBZLObWQ9kn4D2BsR6xpZRwW/HhEzST2Q3ijpE40uiHTUORP4x4iYAbwFNMt5rGHAVcAjTVDLqaSWgynA/wFGSvrdRtYUEZuARcAq4HvAeuC9420zGIHuLgL6QNJQUpgvjYjlja6nu+JP9SeByxtcykXAVZK2kZrwZkl6sLElvX+UR0TsBR4nNTc22g5gR7e/qh4lBXwzuAJ4OiL2NLoQ4BLglYjoiIhDwHLg4w2uiYi4LyLOj4hPAK+Tzqv1ajAC3V0ElCRJpLbOTRHx942uB0BSq6TRxfRJwKXAC42sKSK+EhETImIy6fP0HxHR0KMpSSMljeqcBi4j/cncUBGxG/ippM7e+mYDGxtYUnefpQmaWwqvAhdKGlH8P5xNOofVUJI+UownktrPHzre+oPR22J/ugioO0kPA58ETpe0A7g9Iu5rbFVcBHwOeK5oswb4akT8W+NKYhywpHigyQnAsohoissEm8xY4PGUBbQAD0XE9xpb0vv+GFhaHFBtBX6vwfV0fuldCvxBo2sBiIi1kh4FngYOA8/QHN0APCbpNOAQcGO1E9q+9d/MLBM+KWpmlgkHuplZJhzoZmaZcKCbmWXCgW5mlgkHuplZJhzoZmaZ+P+6nWMySV7nlQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import psutil\n",
    "from time import sleep, strftime\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "from IPython.display import clear_output\n",
    "\n",
    "pltLength = 10\n",
    "x = [i for i in range(pltLength)]\n",
    "y = [None for i in range(pltLength)]\n",
    "\n",
    "fig = plt.figure(figsize=(6,3))\n",
    "# Turn the interactive mode on\n",
    "plt.ion()\n",
    "\n",
    "i = 0\n",
    "def graph(cpu):\n",
    "    global i\n",
    "    if i < pltLength:\n",
    "        y[i] = cpu\n",
    "        i += 1\n",
    "    else:\n",
    "        # queue \n",
    "        # Once enough data is captured,\n",
    "        # append the newest data point at the end \n",
    "        # delete the oldest from the head\n",
    "        y.append(cpu)\n",
    "        del y[0]\n",
    "\n",
    "    # clear the current figure.\n",
    "    plt.clf()\n",
    "    \n",
    "    plt.ylim(0, 80)    \n",
    "    plt.xlim(0, pltLength-1)\n",
    "    plt.plot(x, y, \"b-o\")\n",
    "    \n",
    "    plt.draw()\n",
    "   \n",
    "    # avoid the  screen flicker in figure dynamic display\n",
    "    clear_output(wait=True)\n",
    "    plt.pause(0.05)\n",
    "\n",
    "while True:\n",
    "    # get the cpu_percent\n",
    "    cpu = psutil.cpu_percent()\n",
    "    graph(cpu)\n",
    "    sleep(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#####  2.4.2.2 Array Implementation of Queue in CPP\n",
    "\n",
    "In the queue data structure, we keep an array `double *values`, and the positions `front` and `rear`, which represent the ends of the queue.\n",
    "\n",
    "We set the max number of elements in the queue, `maxSize` and keep track of the number of elements that are actually in the queue, `counter`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/include/queue.h\n",
    "class Queue \n",
    "{\n",
    "\tpublic:\n",
    "\t\tQueue(int size);// constructor\n",
    "\t\t~Queue();// destructor\n",
    "\t\tbool IsEmpty(void);\n",
    "\t\tbool IsFull(void);\n",
    "\t\tbool Enqueue(double x);\n",
    "\t\tbool Dequeue(double &x);\n",
    "\t\tvoid DisplayQueue(void);\n",
    "\tprivate:\n",
    "\t\tint front;// front index\n",
    "\t\tint rear;// rear index\n",
    "\t\tint counter;// number of elements\n",
    "\t\tint maxSize;// size of array queue\n",
    "\t\tdouble* values;// element array\n",
    "};\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/queue.cpp\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/queue.cpp\n",
    "#include <iostream>\n",
    "#include \"queue.h\"\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "Queue::Queue(int size) \n",
    "{\n",
    "\tvalues = new double[size];\n",
    "\tmaxSize = size;\n",
    "\tfront = 0;\n",
    "\trear = -1;\n",
    "\tcounter = 0;\n",
    "}\n",
    "\n",
    "Queue::~Queue() \n",
    "{ \n",
    "\tdelete [] values; \n",
    "}\n",
    "\n",
    "bool Queue::IsEmpty() \n",
    "{\n",
    "\tif (counter)\n",
    "\t\treturn false;\n",
    "\telse \n",
    "\t\treturn true;\n",
    "}\n",
    "\n",
    "bool Queue::IsFull() \n",
    "{\n",
    "\tif (counter < maxSize)\n",
    "\t\treturn false;\n",
    "\telse \n",
    "\t\treturn true;\n",
    "}\n",
    "\n",
    "bool Queue::Enqueue(double x) \n",
    "{\n",
    "\tif (IsFull()) \n",
    "\t{\n",
    "\t\tcout<< \"Error: the queue is full.\" << endl;\n",
    "\t\treturn false;\n",
    "\t}\n",
    "\telse \n",
    "\t{\n",
    "\t\t// calculate the new rear position (circular)\n",
    "\t\trear= (rear + 1) % maxSize; \n",
    "\t\t// insert new item\n",
    "\t\tvalues[rear]= x;\n",
    "\t\t// update counter\n",
    "\t\tcounter++;\n",
    "\t\treturn true;\n",
    "\t}\n",
    "}\n",
    "\n",
    "bool Queue::Dequeue(double &x) \n",
    "{\n",
    "\tif (IsEmpty()) \n",
    "\t{\n",
    "\t\tcout<< \"Error: the queue is empty.\" << endl;\n",
    "\t\treturn false;\n",
    "\t}\n",
    "\telse \n",
    "\t{\n",
    "\t\t// retrieve the front item\n",
    "\t\tx= values[front];\n",
    "\t\t// move front \n",
    "\t\tfront= (front + 1) % maxSize;\n",
    "\t\t// update counter\n",
    "\t\tcounter--;\n",
    "\t\treturn true;\n",
    "\t}\n",
    "}\n",
    "\n",
    "void Queue::DisplayQueue()\n",
    "{\n",
    "\tcout<< \"front -->\";\n",
    "\tfor (int i = 0; i < counter; i++) \n",
    "\t{\n",
    "\t\tif (i == 0) \n",
    "\t\t\tcout << \"\\t\";\n",
    "\t\telse \n",
    "\t\t\tcout << \"\\t\\t\"; \n",
    "\t\tcout<< values[(front + i) % maxSize];\n",
    "\t\tif (i != counter - 1)\n",
    "\t\t\tcout << endl;\n",
    "\t\telse\n",
    "\t\t\tcout << \"\\t<--rear\" << endl;\n",
    "\t}\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/TestQueue.cpp\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/TestQueue.cpp\n",
    "#include <iostream>\n",
    "#include \"queue.h\"\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "int main(void) \n",
    "{\n",
    "\tQueue queue(5);\n",
    "\tcout<< \"Enqueue 5 items.\" << endl;\n",
    "\tfor (int x = 0; x < 5; x++)\n",
    "\t\tqueue.Enqueue(x);\n",
    "\tcout<< \"Now attempting to enqueue again...\" << endl;\n",
    "\tqueue.Enqueue(5);\n",
    "\tqueue.DisplayQueue();\n",
    "\tdouble value;\n",
    "\tqueue.Dequeue(value);\n",
    "\tcout<< \"Retrieved element = \" << value << endl;\n",
    "\tqueue.DisplayQueue();\n",
    "\tqueue.Enqueue(7);\n",
    "\tqueue.DisplayQueue();\n",
    "\treturn 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -w -o ./demo/bin/TestQueue ./demo/src/TestQueue.cpp  ./demo/src/queue.cpp -I./demo/include/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enqueue 5 items.\n",
      "Now attempting to enqueue again...\n",
      "Error: the queue is full.\n",
      "front -->\t0\n",
      "\t\t1\n",
      "\t\t2\n",
      "\t\t3\n",
      "\t\t4\t<--rear\n",
      "Retrieved element = 0\n",
      "front -->\t1\n",
      "\t\t2\n",
      "\t\t3\n",
      "\t\t4\t<--rear\n",
      "front -->\t1\n",
      "\t\t2\n",
      "\t\t3\n",
      "\t\t4\n",
      "\t\t7\t<--rear\n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\TestQueue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2.4.2.3 std:queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/demo_std_queue.cpp\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/demo_std_queue.cpp\n",
    "#include <iostream>\n",
    "#include <queue> \n",
    "using namespace std;\n",
    "int main()\n",
    "{\n",
    "    queue<int> queue_sample;\n",
    "    for (int x = 0; x < 5; x++)\n",
    "        queue_sample.push(x);\n",
    "    \n",
    "     while (!queue_sample.empty()) {\n",
    "        cout << ' ' << queue_sample.front();\n",
    "        queue_sample.pop();\n",
    "    }\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -o ./demo/bin/demo_std_queue ./demo/src/demo_std_queue.cpp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 1 2 3 4\n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\demo_std_queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Non-Linear Data Structures\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Tree\n",
    "\n",
    "In the linear data structures you have studied thus far, all items except for the first have a distinct predecessor, and all items except the last have a distinct successor. \n",
    "\n",
    "In a tree, the ideas of predecessor and successor are replaced with those of `parent` and `child`.\n",
    "\n",
    "Trees have two main characteristics:\n",
    "\n",
    "* Each item can have multiple children.\n",
    "\n",
    "* All items, except a privileged item called the root, have exactly one parent. The root has no parent.\n",
    "\n",
    "#### 3.1.1 Tree Terminology\n",
    "\n",
    "Tree terminology is a peculiar mix of biological, genealogical, and geometric terms. \n",
    "\n",
    "\n",
    "* **Node(节点)**: An **item** stored in a tree.\n",
    "\n",
    "\n",
    "* **Root(根)**: The **topmost** node in a tree. lt is the only node without a parent.\n",
    "\n",
    "\n",
    "* **Parent(父)** A node immediately **above** and directly connected to a given node. A node can have only one parent.\n",
    "\n",
    "\n",
    "* **Child(子)**: A node immediately **below** and directly connected to a given node. A node can have more than one child, and its children are viewed as organized in left-to-right order.The leftmost child is called the first child, and the rightmost is called the last child.\n",
    "\n",
    "\n",
    "* **Leaf(叶)**: A node that has **no** children.\n",
    "\n",
    "\n",
    "* **Edge(边)**: The line that connects a parent to its child.\n",
    "\n",
    "\n",
    "* **Path(路径)**: an ordered list of nodes that are connected by edges\n",
    "\n",
    "\n",
    "* **Siblings(兄弟)**: The children of a common parent.\n",
    "\n",
    "\n",
    "* **Subtree(子树）** a set of nodes and edges comprised of a parent and all the descendants of that parent.\n",
    "\n",
    "\n",
    "* **Level(层次)**: The level of a node $𝑛$ is the number of edges on the path from the **root** node to $𝑛$. By definition, the level of the root node is zero.\n",
    "\n",
    "\n",
    "* **Height(高度):** The length of the longest path in the tree; put differently, the `maximum level number` among leaves in the tree.\n",
    "\n",
    "A tree with `only the root node` is called a `null(empty)` tree.\n",
    "\n",
    "The Figure shows a tree and some of its properties.\n",
    "\n",
    "\n",
    "![](./img/ds/tree.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.1.2  Binary Trees(二叉树)\n",
    "\n",
    "In a binary tree, each node has at **most** two children, referred to as the left child and the right child.\n",
    "\n",
    "In a binary tree, when a node has only one child, you distinguish it as being either a left child or a right child.\n",
    "\n",
    ">二叉树:每个结点最多只能有两棵子树，且有左右之分\n",
    "\n",
    "* **Perfectly balanced binary tree(完美平衡二叉树)**: includes a complete complement of nodes at each level `but the last one `\n",
    "\n",
    ">只有最后一层可能不满，其他层都是满的\n",
    "\n",
    "* **Complete binary tree(完全二叉树)**: every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible\n",
    "\n",
    ">除最后一层外，每一层的结点数达到最大值，并且最下面一层的结点都集中在该层最`左边`二叉树\n",
    "\n",
    "* **Full binary tree（满二叉树）** contains the maximum number of nodes for a given height H.\n",
    "\n",
    ">最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树\n",
    "\n",
    "![](./img/ds/binarytrees.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "#### 3.1.3  Binary Tree Traversals\n",
    "\n",
    "There are three types of traversals for binary trees: preorder, inorder, postorder\n",
    "\n",
    "Each type of traversal follows a particular path and direction as it visits the nodes in the tree. \n",
    "\n",
    "\n",
    "\n",
    "* **Pre-order(前序)**: visit the **root**, traverse the left subtree, then the right subtree. \n",
    "\n",
    "![Pre-order](./img/ds/preorder.png)\n",
    "\n",
    "* **In-order(中序):**  traverse the left subtree, visit the **root**, then the right subtree.\n",
    "\n",
    "![in-order](./img/ds/inorder.png)\n",
    "\n",
    ">we can retrieve the sorted list or perform searching via `in-order traversal`. \n",
    ">\n",
    ">**二叉查找树的中序遍历序列一定是从小到大排列的**\n",
    ">\n",
    "\n",
    "* **Post-order(后序):**  traverse the left subtree, the right subtree, then visit the **root**.\n",
    "\n",
    "![Post-order](./img/ds/postorder.png)\n",
    "\n",
    "**Pre-**, **in-** and **post-** refer to \n",
    "\n",
    "* the `order` of visiting the **root**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Binary Tree in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, left=None,right=None,data=None):\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.data = data\n",
    "   \n",
    "    def getTree_inorder(self):\n",
    "        \"\"\"in-order\"\"\"\n",
    "        if self.left:\n",
    "            self.left.getTree_inorder()\n",
    "        print(self.data,end=\" \")\n",
    "        if self.right:\n",
    "            self.right.getTree_inorder()\n",
    "    \n",
    "    def print_tree(self):\n",
    "        \"\"\"in-order\"\"\"\n",
    "        print(\"In-order{\",end=\" \")\n",
    "        self.getTree_inorder()\n",
    "        print(\"}\")   \n",
    "    \n",
    "    def getTree_preorder(self):\n",
    "        \"\"\"pre-order\"\"\"\n",
    "        print(self.data,end=\" \")\n",
    "        if self.left:\n",
    "            self.left.getTree_preorder()\n",
    "        if self.right:\n",
    "            self.right.getTree_preorder()\n",
    "    \n",
    "    def print_tree_preorder(self):\n",
    "        \"\"\"preorder\"\"\"\n",
    "        print(\"pre-order {\",end=\" \")\n",
    "        self.getTree_preorder()\n",
    "        print(\"}\")\n",
    "            \n",
    "\n",
    "    def getTree_postorder(self):\n",
    "        \"\"\"post-order\"\"\"\n",
    "        if self.left:\n",
    "            self.left.getTree_postorder()\n",
    "        if self.right:\n",
    "            self.right.getTree_postorder()\n",
    "        print(self.data,end=\" \")\n",
    "    \n",
    "    def print_tree_postorder(self):\n",
    "        \"\"\"postorder\"\"\"\n",
    "        print(\"post-order {\",end=\" \")\n",
    "        self.getTree_postorder()\n",
    "        print(\"}\")    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = Tree(None,None,'G')\n",
    "e = Tree(None,None, 'E')\n",
    "a = Tree(None,None, 'A')\n",
    "c = Tree(None,None, 'C')\n",
    "b = Tree(a,c, 'B')\n",
    "f = Tree(e,g, 'F')\n",
    "root = Tree(b,f, 'D')\n",
    "root.print_tree()\n",
    "root.print_tree_preorder()\n",
    "root.print_tree_postorder()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "![DS_Bstchar](./img/ds/bst-char.png)\n",
    "\n",
    "In-order: traverse the left subtree, visit the root, then the right subtree.\n",
    "\n",
    "* A B C `D` E F G\n",
    "\n",
    "pre-order : visit the root, traverse the left subtree, then the right subtree.\n",
    "\n",
    "* `D` B A C F E G \n",
    "\n",
    "post-order:traverse the left subtree, the right subtree, then visit the root.\n",
    "\n",
    "* A C B E G F `D`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Binary Tree in CPP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/simplebinarytree.cpp\n",
    "\n",
    "/*\n",
    "g++ -o simplebinarytree simplebinarytree.cpp\n",
    "./simplebinarytree\n",
    "*/\n",
    "#include <iostream>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "template <typename T>\n",
    "class Node\n",
    "{\n",
    "public:\n",
    "    T data;\n",
    "    Node *left;\n",
    "    Node *right;\n",
    "\n",
    "    Node()\n",
    "    {\n",
    "    }\n",
    "\n",
    "    Node(Node *ileft, Node *iright, const T d)\n",
    "    {\n",
    "        data = d;\n",
    "        if (ileft != NULL)\n",
    "        {\n",
    "            Node *left = new Node();\n",
    "        }\n",
    "        left = ileft;\n",
    "        if (iright != NULL)\n",
    "            Node *right = new Node();\n",
    "        right = iright;\n",
    "    }\n",
    "    \n",
    "    ~Node()\n",
    "    {\n",
    "        if (left != NULL)\n",
    "            delete left;\n",
    "        if (right != NULL)\n",
    "            delete right;\n",
    "    }\n",
    "\n",
    "    void getTree_inorder()\n",
    "    {\n",
    "        if (left != NULL)\n",
    "            left->getTree_inorder();\n",
    "        cout << data << \" \";\n",
    "        if (right != NULL)\n",
    "            right->getTree_inorder();\n",
    "    }\n",
    "\n",
    "    void print_tree()\n",
    "    {\n",
    "        cout << \"In-order{\"\n",
    "             << \" \";\n",
    "        getTree_inorder();\n",
    "        cout << \"}\" << endl;\n",
    "    }\n",
    "\n",
    "    void getTree_preorder()\n",
    "    {\n",
    "        cout << data << \" \";\n",
    "        if (left != NULL)\n",
    "            left->getTree_preorder();\n",
    "        if (right != NULL)\n",
    "            right->getTree_preorder();\n",
    "    }\n",
    "\n",
    "    void print_tree_preorder()\n",
    "    {\n",
    "        cout << \"pre-order{\"\n",
    "             << \" \";\n",
    "        getTree_preorder();\n",
    "        cout << \"}\" << endl;\n",
    "    }\n",
    "\n",
    "    void getTree_postorder()\n",
    "    {\n",
    "        if (left != NULL)\n",
    "            left->getTree_postorder();\n",
    "        if (right != NULL)\n",
    "            right->getTree_postorder();\n",
    "        cout << data << \" \";\n",
    "    }\n",
    "\n",
    "    void print_tree_postorder()\n",
    "    {\n",
    "        cout << \"post-order{\"\n",
    "             << \" \";\n",
    "        getTree_postorder();\n",
    "        cout << \"}\" << endl;\n",
    "    }\n",
    "};\n",
    "\n",
    "int main()\n",
    "{\n",
    "    Node<char> *g = new Node<char>(NULL, NULL, 'G');\n",
    "    Node<char> *e = new Node<char>(NULL, NULL, 'E');\n",
    "    Node<char> *a = new Node<char>(NULL, NULL, 'A');\n",
    "    Node<char> *c = new Node<char>(NULL, NULL, 'C');\n",
    "    Node<char> *b = new Node<char>(a, c, 'B');\n",
    "    Node<char> *f = new Node<char>(e, g, 'F');\n",
    "    Node<char> *root = new Node<char>(b, f, 'D');\n",
    "    root->print_tree();\n",
    "    root->print_tree_preorder();\n",
    "    root->print_tree_postorder();\n",
    "    delete g;\n",
    "    delete e;\n",
    "    delete a;\n",
    "    delete c;\n",
    "    delete b;\n",
    "    delete f;\n",
    "    delete root;\n",
    "    return 0;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    " !g++ -o ./demo/bin/simplebinarytree ./demo/src/simplebinarytree.cpp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\simplebinarytree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Binary Search Tree(二叉查找树)\n",
    "\n",
    "<b style=\"color:blue\">Trees emphasize the `parent/child` relationship, which allows users to `order data according to criteria` other than position.</b>\n",
    "\n",
    "The **Binary Search Tree(BST 二叉查找树)** imposes a sorted ordering on its nodes\n",
    "\n",
    "A binary search tree, **without** duplicate elements, has these properties:\n",
    "\n",
    "* All values in the `left` subtree are `smaller` than the parent node.\n",
    "\n",
    "* All values in the `right` subtree are `larger` than the parent node.\n",
    "\n",
    ">每棵子树`头节点`的值都比各自`左子树`上所有节点值要`大`，也都比各自`右子树`上所有节点值要`小`。\n",
    "\n",
    "When the shape of a BST approaches that of a perfectly balanced binary tree, searches and insertions are $O(logn)$ in the worst case.\n",
    "\n",
    "The following diagrams illustrate two binary search trees.\n",
    "\n",
    "![DS_Bst-num](./img/ds/DS_BinaryTree.png)\n",
    "\n",
    "![DS_Bstchar](./img/ds/bst-char.png)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.3.1 BST in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSTree(Tree):\n",
    "    def __init__(self, data):\n",
    "        super().__init__(None,None,data)\n",
    "        #self.left = None\n",
    "        #self.right = None\n",
    "        #self.data = data\n",
    "   \n",
    "    def insert(self, data):\n",
    "        if self.data:\n",
    "            if data < self.data:\n",
    "                if self.left is None:\n",
    "                    self.left =  BSTree(data)\n",
    "                else:\n",
    "                    self.left.insert(data)\n",
    "            elif data > self.data:\n",
    "                if self.right is None:\n",
    "                    self.right = BSTree(data)\n",
    "                else:\n",
    "                    self.right.insert(data)\n",
    "        else:\n",
    "            self.data = data\n",
    "\n",
    "        \n",
    "    def find_min(self):\n",
    "        if self.left:\n",
    "            return self.left.find_min()\n",
    "        else:\n",
    "            return self.data\n",
    "    \n",
    "    def find_max(self):\n",
    "        if self.right:\n",
    "            return self.right.find_max()\n",
    "        else:\n",
    "            return self.data\n",
    "   \n",
    "    def query(self, data):\n",
    "        if data == None:\n",
    "            return False\n",
    "        if self.data == data:\n",
    "            return True\n",
    "        elif data < self.data:\n",
    "            if self.left is None:\n",
    "                return False\n",
    "            else:\n",
    "                return self.left.query(data)\n",
    "        elif data > self.data:\n",
    "            if self.right is None:\n",
    "                return False\n",
    "            else:\n",
    "                return self.right.query(data)\n",
    "    \n",
    "    def delete(self, data):\n",
    "        \"\"\" delete the node with the given data and return the  root node of the tree \"\"\"\n",
    "        if self.data == data:\n",
    "        # found the node we need to delete\n",
    "            if self.right and self.left: \n",
    "                # get the successor node and its parent \n",
    "                [psucc, succ] = self.right._findMin(self)\n",
    "                # splice out the successor,we need the parent to do this \n",
    "                if psucc.left == succ:\n",
    "                    psucc.left = succ.right\n",
    "                else:\n",
    "                    psucc.right = succ.right\n",
    "                \n",
    "                # reset the left and right children of the successor\n",
    "                succ.left = self.left\n",
    "                succ.right = self.right\n",
    "                return succ                \n",
    "            else:\n",
    "                # easier case\n",
    "                if self.left:\n",
    "                    return self.left    # promote the left subtree\n",
    "                else:\n",
    "                    return self.right   # promote the right subtree \n",
    "        else:\n",
    "            if self.data> data:          # data should be in the left subtree\n",
    "                if self.left:\n",
    "                    self.left = self.left.delete(data)\n",
    "                # else data key is not in the tree \n",
    "            else:                       # data should be in the right subtree\n",
    "                if self.right:\n",
    "                    self.right = self.right.delete(data)\n",
    "\n",
    "        return self\n",
    "\n",
    "    def _findMin(self, parent):\n",
    "        \"\"\" return the minimum node in the current tree and its parent \"\"\"\n",
    "        # the parent node is passed in as an argument\n",
    "        # so that eventually when the leftmost child is reached, the \n",
    "        # call can return both the parent to the successor and the successor\n",
    "        if self.left:\n",
    "            return self.left._findMin(self)\n",
    "        else:\n",
    "            return [parent, self]           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "root = BSTree(\"D\")\n",
    "root.insert(\"B\");\n",
    "root.insert(\"F\");\n",
    "root.insert(\"A\");\n",
    "root.insert(\"C\");\n",
    "root.insert(\"G\");\n",
    "root.insert(\"E\");\n",
    ";\n",
    "root.print_tree()\n",
    "root.print_tree_preorder()\n",
    "root.print_tree_postorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(root.query(\"B\"))\n",
    "print(root.query(\"P\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(root.find_min())\n",
    "print(root.find_max())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "r=root.delete(\"C\")\n",
    "r.print_tree()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = BSTree(6)\n",
    "root.insert(10);\n",
    "root.insert(5);\n",
    "root.insert(15);\n",
    "root.insert(7);\n",
    "root.insert(4);\n",
    "root.insert(9);\n",
    "root.print_tree()\n",
    "root.print_tree_preorder()\n",
    "root.print_tree_postorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(root.query(15))\n",
    "print(root.query(100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(root.find_min())\n",
    "print(root.find_max())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "r=root.delete(9)\n",
    "r.print_tree()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![DS_Bst-num](./img/ds/DS_BinaryTree.png)\n",
    "In-order: traverse the left subtree, visit the root, then the right subtree.\n",
    "\n",
    "* 4 -> 5 -> `6` -> 7 -> 9 ->10 -> 15.\n",
    "\n",
    "Pre-order: visit the root, traverse the left subtree, then the right subtree.\n",
    "\n",
    "* `6` -> 5 -> 4 -> 10 -> 7 -> 9 ->15.\n",
    "\n",
    "Post-order: traverse the left subtree, the right subtree, then visit the root.\n",
    "\n",
    "\n",
    "* 4 -> 5 -> 9 -> 7 -> 15 -> 10 -> `6`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.3.2 BST In C++\n",
    "\n",
    "**Node template class for binary tree**\n",
    "\n",
    "* Node.h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/include/Node.h\n",
    "/* \n",
    "   Node template class for binary tree (Node.h)\n",
    "*/\n",
    "#ifndef NODE_H\n",
    "#define NODE_H\n",
    " \n",
    "template <typename T> class BinaryTree; // Forward reference\n",
    " \n",
    "template <typename T>\n",
    "class Node {\n",
    "private:\n",
    "   T data;\n",
    "   Node * rightPtr;\n",
    "   Node * leftPtr;\n",
    "public:\n",
    "   Node (T d) : data(d), rightPtr(0), leftPtr(0) { };\n",
    "   T getData() const { return data; };\n",
    "   Node * getRightPtr() const { return rightPtr; }\n",
    "   Node * getLeftPtr() const  { return leftPtr;  }\n",
    " \n",
    "friend class BinaryTree<T>;\n",
    "   // Make BinaryTree class a friend to access private data\n",
    "};\n",
    " \n",
    "#endif"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**BinaryTree template class for binary tree: BinaryTree.h**\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/include/BinaryTree.h\n",
    "/* \n",
    "   BinaryTree template class for binary tree (BinaryTree.h)\n",
    "*/\n",
    "#ifndef BINARY_TREE_H\n",
    "#define BINARY_TREE_H\n",
    "\n",
    "#include <iostream>\n",
    "#include <queue>\n",
    "#include \"Node.h\"\n",
    "\n",
    "// Forward Reference\n",
    "template <typename T>\n",
    "std::ostream &operator<<(std::ostream &os, const BinaryTree<T> &lst);\n",
    "\n",
    "template <typename T>\n",
    "class BinaryTree\n",
    "{\n",
    "private:\n",
    "   Node<T> *rootPtr;\n",
    "\n",
    "   // private helper functions\n",
    "   void insertNode(Node<T> *&ptr, const T &value);\n",
    "   void preOrderSubTree(const Node<T> *ptr, std::ostream &os = std::cout) const;\n",
    "   void inOrderSubTree(const Node<T> *ptr, std::ostream &os = std::cout) const;\n",
    "   void postOrderSubTree(const Node<T> *ptr, std::ostream &os = std::cout) const;\n",
    "   void removeSubTree(Node<T> *&ptr);\n",
    "\n",
    "public:\n",
    "   BinaryTree();  // Constructor\n",
    "   ~BinaryTree(); // Destructor\n",
    "   void insert(const T &value);\n",
    "   bool isEmpty() const;\n",
    "   void preOrderTraversal(std::ostream &os = std::cout) const;\n",
    "   void inOrderTraversal(std::ostream &os = std::cout) const;\n",
    "   void postOrderTraversal(std::ostream &os = std::cout) const;\n",
    "\n",
    "   friend std::ostream &operator<<<>(std::ostream &os, const BinaryTree<T> &lst);\n",
    "   // Overload the stream insertion operator to print the list\n",
    "};\n",
    "\n",
    "// Constructor - Create an empty list with no node\n",
    "template <typename T>\n",
    "BinaryTree<T>::BinaryTree() : rootPtr(0) {}\n",
    "\n",
    "// Destructor - Remove all the dynamically allocated nodes\n",
    "template <typename T>\n",
    "BinaryTree<T>::~BinaryTree()\n",
    "{\n",
    "   removeSubTree(rootPtr);\n",
    "   // std::cout << \"Destructor completed...\" << std::endl;\n",
    "}\n",
    "\n",
    "template <typename T>\n",
    "void BinaryTree<T>::removeSubTree(Node<T> *&ptr)\n",
    "{\n",
    "   if (ptr)\n",
    "   {\n",
    "      removeSubTree(ptr->leftPtr);  // remove left subtree\n",
    "      removeSubTree(ptr->rightPtr); // remove right subtree\n",
    "      delete ptr;\n",
    "   }\n",
    "}\n",
    "\n",
    "// Is list empty? Check if rootPtr is null\n",
    "template <typename T>\n",
    "bool BinaryTree<T>::isEmpty() const { return rootPtr == 0; }\n",
    "\n",
    "// Push the data in front by dynamically allocate a new node\n",
    "template <typename T>\n",
    "void BinaryTree<T>::insert(const T &value)\n",
    "{\n",
    "   insertNode(rootPtr, value);\n",
    "}\n",
    "\n",
    "// Need to pass the pointer by reference so as to modify the caller's copy\n",
    "template <typename T>\n",
    "void BinaryTree<T>::insertNode(Node<T> *&ptr, const T &value)\n",
    "{\n",
    "   if (ptr == 0)\n",
    "   {\n",
    "      ptr = new Node<T>(value);\n",
    "   }\n",
    "   else\n",
    "   {\n",
    "      if (value < ptr->data)\n",
    "         insertNode(ptr->leftPtr, value);\n",
    "      else if (value > ptr->data)\n",
    "         insertNode(ptr->rightPtr, value);\n",
    "      else\n",
    "         std::cout << \"duplicate value\" << std::endl;\n",
    "   }\n",
    "}\n",
    "\n",
    "template <typename T>\n",
    "void BinaryTree<T>::preOrderTraversal(std::ostream &os) const\n",
    "{\n",
    "   os << \"{ \";\n",
    "   preOrderSubTree(rootPtr);\n",
    "   os << '}' << std::endl;\n",
    "}\n",
    "\n",
    "template <typename T>\n",
    "void BinaryTree<T>::preOrderSubTree(const Node<T> *ptr, std::ostream &os) const\n",
    "{\n",
    "   if (ptr)\n",
    "   {\n",
    "      os << ptr->data << ' ';\n",
    "      preOrderSubTree(ptr->leftPtr);\n",
    "      preOrderSubTree(ptr->rightPtr);\n",
    "   }\n",
    "}\n",
    "\n",
    "template <typename T>\n",
    "void BinaryTree<T>::inOrderTraversal(std::ostream &os) const\n",
    "{\n",
    "   os << \"{ \";\n",
    "   inOrderSubTree(rootPtr);\n",
    "   os << '}' << std::endl;\n",
    "}\n",
    "\n",
    "template <typename T>\n",
    "void BinaryTree<T>::inOrderSubTree(const Node<T> *ptr, std::ostream &os) const\n",
    "{\n",
    "   if (ptr)\n",
    "   {\n",
    "      inOrderSubTree(ptr->leftPtr);\n",
    "      os << ptr->data << ' ';\n",
    "      inOrderSubTree(ptr->rightPtr);\n",
    "   }\n",
    "}\n",
    "\n",
    "template <typename T>\n",
    "void BinaryTree<T>::postOrderTraversal(std::ostream &os) const\n",
    "{\n",
    "   os << \"{ \";\n",
    "   postOrderSubTree(rootPtr);\n",
    "   os << '}' << std::endl;\n",
    "}\n",
    "\n",
    "template <typename T>\n",
    "void BinaryTree<T>::postOrderSubTree(const Node<T> *ptr, std::ostream &os) const\n",
    "{\n",
    "   if (ptr)\n",
    "   {\n",
    "      postOrderSubTree(ptr->leftPtr);\n",
    "      postOrderSubTree(ptr->rightPtr);\n",
    "      os << ptr->data << ' ';\n",
    "   }\n",
    "}\n",
    "\n",
    "// Overload the stream insertion operator to print the list in in-order traversal\n",
    "template <typename T>\n",
    "std::ostream &operator<<(std::ostream &os, const BinaryTree<T> &lst)\n",
    "{\n",
    "   lst.inOrderTraversal(os);\n",
    "   return os;\n",
    "}\n",
    "\n",
    "#endif\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Test Driver for BinaryTree class :TestBinaryTree.cpp**\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/TestBinaryTree.cpp\n",
    "/* \n",
    "\n",
    "Test Driver for BinaryTree class (TestBinaryTree.cpp) \n",
    "    \n",
    "*/\n",
    "#include <iostream>\n",
    "#include \"BinaryTree.h\"\n",
    "using namespace std;\n",
    " \n",
    "int main() {\n",
    "   BinaryTree<int> t1;\n",
    "   t1.insert(6);\n",
    "   t1.insert(10);\n",
    "   t1.insert(5);\n",
    "   t1.insert(15);\n",
    "   t1.insert(7);\n",
    "   t1.insert(4);\n",
    "   t1.insert(9);\n",
    " \n",
    "   cout<<\"pre-order depth-first search\"<<endl;\n",
    "   t1.preOrderTraversal();\n",
    "   cout<<\"in-order depth-first search (ascending order)\"<<endl;\n",
    "   t1.inOrderTraversal();\n",
    "   cout<<\"post-order depth-first search\"<<endl;\n",
    "   t1.postOrderTraversal();\n",
    "   cout<<\"in-order depth-first search\"<<endl;\n",
    "   cout<<t1;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -w -o ./demo/bin/TestBinaryTree ./demo/src/TestBinaryTree.cpp -I./demo/include/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\TestBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4  Heap（堆）\n",
    "\n",
    "A heap is a **complete binary tree(完全二叉树)** that satisfies the  heap property.\n",
    "\n",
    "#### 3.4.1 The heap property\n",
    "\n",
    "The heap property says that is the value of Parent is either `greater than or equal` to (in a `max` heap ) or `less than or equal` to (in a `min` heap) the value of the Child.\n",
    "\n",
    "**Binary heaps(二叉堆) can be represented using a list or array organized** so that\n",
    "\n",
    "* the children of element N are at positions 2 * N + 1 and 2 * N + 2 (for zero-based indexes).\n",
    "\n",
    "This layout makes it possible to rearrange heaps in place, so it is not necessary to reallocate as much memory when adding or removing items.\n",
    "\n",
    ">堆中某个结点的值总是不大于或不小于其父结点的值\n",
    ">\n",
    ">堆总是一棵完全二叉树\n",
    "\n",
    "\n",
    "#### 3.4.2 Max and Min Heap\n",
    "\n",
    "There are two types of heaps\n",
    "\n",
    "* the max heap(最大堆)\n",
    "* the min heap(最小堆)\n",
    "\n",
    "In a max heap, the key present at the **root is the largest** in the heap and all the values below this are less than this value.\n",
    "\n",
    "\n",
    "In a min heap, the key present at the **root is the smallest** in the heap and all the values below this are greater than this value.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "![heap](./img/ds/heap.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "max_heapify(A,i)\n",
    "```cpp\n",
    "l = left(i)\n",
    "r = right(i)\n",
    "if l<=heap-size[A] and A[l]>A[i] then\n",
    "    largest = l\n",
    "else \n",
    "    largest = i\n",
    "end if    \n",
    "if r<=heap-size[A] and A[r]>A[largest] then\n",
    "     largest = r\n",
    "end if     \n",
    "if largest != i then\n",
    "     exchange A[i] and A[largest]\n",
    "     max_heapify(A,largest)\n",
    "end if     \n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[86, 70, 66, 46, 44, 45, 47]\n"
     ]
    }
   ],
   "source": [
    "def left(i):\n",
    "    return 2 * i + 1\n",
    "\n",
    "def right(i):\n",
    "    return 2 * i + 2\n",
    "\n",
    "def max_heapify(A: list, i: int, heap_size=None):\n",
    "    if not heap_size:\n",
    "        heap_size = len(A)\n",
    " \n",
    "    l = left(i)\n",
    "    r = right(i)\n",
    "    if l < heap_size and A[l] > A[i]:\n",
    "        largest = l\n",
    "    else:\n",
    "        largest = i\n",
    "    if r < heap_size and A[r] > A[largest]:\n",
    "        largest = r\n",
    "  \n",
    "    if largest != i:\n",
    "        A[i], A[largest] = A[largest], A[i]\n",
    "        max_heapify(A, largest, heap_size)\n",
    "\n",
    "def build_max_heap(A, heap_size=None):\n",
    "    if not heap_size:\n",
    "        heap_size = len(A)\n",
    "    i = int(heap_size / 2) - 1\n",
    "    while i >= 0:\n",
    "        max_heapify(A, i, heap_size)\n",
    "        i -= 1\n",
    "\n",
    "A=[47,70,86, 46,44,45,66]\n",
    "build_max_heap(A)\n",
    "print(A)           "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 3.4.2.1 PriorityQueue\n",
    "\n",
    "\n",
    "```\n",
    "from queue import PriorityQueue \n",
    "```\n",
    "PriorityQueue\n",
    "优先队列：the lowest first 最小先出 （minheap最小堆）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "44 45 46 47 66 70 86 "
     ]
    }
   ],
   "source": [
    "from queue import PriorityQueue \n",
    " \n",
    "pq = PriorityQueue()\n",
    "pq.put(47)\n",
    "pq.put(70)\n",
    "pq.put(86)\n",
    "pq.put(46)\n",
    "pq.put(44)\n",
    "pq.put(45)\n",
    "pq.put(66)\n",
    " \n",
    "while not pq.empty():\n",
    "    print(pq.get(),end=\" \")   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 3.4.2.2 std::queue priority_queue\n",
    "\n",
    "* std::queue priority_queue： 默认的是大顶堆 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/priority_queue.cpp\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/priority_queue.cpp\n",
    "\n",
    "#include <iostream>\n",
    "#include <queue>\n",
    "using namespace std; \n",
    "\n",
    "int main()\n",
    "{\n",
    "    priority_queue<float> q;  // 默认的是大顶堆 \n",
    "    // insert three elements into the priority queue\n",
    "    q.push(47);\n",
    "    q.push(70);\n",
    "    q.push(86); \n",
    "    // print the elements\n",
    "    while (!q.empty())\n",
    "    {\n",
    "        cout << q.top() << ' ';\n",
    "        q.pop();\n",
    "    }\n",
    "    cout << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -o ./demo/bin/priority_queue ./demo/src/priority_queue.cpp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "86 70 47 \n"
     ]
    }
   ],
   "source": [
    "! .\\demo\\bin\\priority_queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.4.3 Heap Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Heaps can be used in sorting an array. In max-heaps, maximum element will always be at the root. Heap Sort uses this property of heap to sort the array.\n",
    "\n",
    "Consider an array $Arr$ which is to be sorted using Heap Sort.\n",
    "\n",
    "* Initially build a max heap of elements in $Arr$\n",
    "\n",
    "* The root element, that is  $Arr[0]$, will contain maximum element of $Arr$. After that, swap this element with the last element of   $Arr$ and heapify the max heap excluding the last element which is already in its correct position and then decrease the length of heap by one.\n",
    "\n",
    "* Repeat the step 2, until all the elements are in their correct position.\n",
    "\n",
    "**Complexity**:\n",
    "\n",
    "max_heapify has complexity$O(logN)$ , build max heap has complexity$O(N)$  and we run max_heapify $N-1$ times in heapsort function, therefore complexity of heapsort function is $O(NlogN)$.\n",
    "\n",
    "堆排序的方法:\n",
    "\n",
    "* 把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### heap sort in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_sort(A, heap_size=None):\n",
    "    if not heap_size:\n",
    "        heap_size = len(A)\n",
    "    build_max_heap(A)\n",
    "    start = heap_size - 1\n",
    "    for i in range(start, 0, -1):\n",
    "        A[0], A[i] = A[i], A[0]\n",
    "        heap_size -= 1\n",
    "        max_heapify(A, 0, heap_size=heap_size)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A=[47,70,86, 46,44,45,66]\n",
    "heap_sort(A)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### heapsort.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/heapsort.c\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "\n",
    "void max_heapify(int arr[], int n, int i) \n",
    "{ \n",
    "    int largest = i; \n",
    "    int l = 2*i + 1; // left = 2*i + 1 \n",
    "    int r = 2*i + 2; // right = 2*i + 2 \n",
    "  \n",
    "    if (l < n && arr[l] > arr[largest]) \n",
    "        largest = l; \n",
    "  \n",
    "    if (r < n && arr[r] > arr[largest]) \n",
    "        largest = r; \n",
    "    \n",
    "    int temp;\n",
    "    if (largest != i) \n",
    "    { \n",
    "        temp = arr[i];\n",
    "        arr[i] = arr[largest];\n",
    "        arr[largest] = temp; \n",
    "        max_heapify(arr, n, largest); \n",
    "    } \n",
    "} \n",
    "\n",
    "void heapSort(int arr[], int n) \n",
    "{ \n",
    "    for (int i = n / 2 - 1; i >= 0; i--) \n",
    "        max_heapify(arr, n, i); \n",
    "  \n",
    "    int temp;\n",
    "    for (int i=n-1; i>=0; i--) \n",
    "    { \n",
    "        temp = arr[0];\n",
    "        arr[0] = arr[i];\n",
    "        arr[i] = temp; \n",
    "        max_heapify(arr, i, 0); \n",
    "    } \n",
    "} \n",
    "\n",
    "void print(const int a[], int iLeft, int iRight) {\n",
    "   printf(\"{\");\n",
    "   for (int i = iLeft; i <= iRight; ++i) {\n",
    "      printf(\"%d\", a[i]);\n",
    "      if (i < iRight) printf(\",\");\n",
    "   }\n",
    "   printf(\"}\\n\");\n",
    "}\n",
    "\n",
    "\n",
    "int main() {\n",
    "   const int SIZE = 7;\n",
    "   int a[] = {47,70,86, 46,44,45,66};\n",
    " \n",
    "   print(a, 0,SIZE-1);\n",
    "   heapSort(a, SIZE);\n",
    "   print(a, 0,SIZE-1);\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -w -o ./demo/bin/heapsort ./demo/src/heapsort.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\heapsort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.5 Hash Tables\n",
    "\n",
    "* [Hash Tables](./UnitDS-5-Hash_Tables.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.6 Graphs\n",
    "\n",
    "\n",
    "* [Graph Optimization Problems](./UnitDS-6-Graph_Optimization_Problems.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.7"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "200.198px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
